1. Field of the Invention
The present invention relates to a dithering device for converting a multi-gradation image (multi-bit pixel value image) into a monochrome or binary image (one-bit pixel value image) through comparison using a dither matrix and, in particular, to a technique for locating elements, i.e. threshold values, in the dither matrix with respect to corresponding pixels of the multi-gradation image.
2. Description of the Prior Art
As one of techniques for converting an image represented by pixels each having a multi-bit or multi-gradation value into an image having pixels each represented by one of only two gradations, i.e. white or black, there has been available a dithering method. In the dithering method, a dither matrix having a plurality of elements each assigned a corresponding threshold value is logically overlaid upon a multi-gradation image for comparison between the threshold values of the dither matrix and values of corresponding pixels of the multi-gradation image. Then, when the value of the pixel of the multi-gradation image is greater than the corresponding threshold value, that pixel is set to black. On the other hand, when the value of the pixel is not greater than the corresponding threshold value, that pixel is set to white. In this fashion, the multi-gradation image is converted into the white/black binary image, which is called "dithering".
In the following explanation, a position of a pixel on a multi-gradation image is represented by coordinates (X, Y), a position of an element (hereinafter referred to as "index") on a dither matrix corresponding to a pixel (X, Y) is represented by coordinates (Px, Py), and lengths of the dither matrix in Px-axis and Py-axis directions are represented by DSx and DSy, respectively.
There have been available two methods for determining a corresponding index in the dithering, that is, a modulo arithmetic method and a conditional branching method.
The modulo arithmetic method is carried out in the following manner:
For dithering a pixel (X, Y), remainder of division (X/DSx) is set to Px, remainder of division (Y/DSy) is set to Py, then a value of the pixel (X, Y) and a threshold value of an index (Px, Py) are compared with each other so as to assign a binary value (white or black) to the pixel.
On the other hand, the conditional branching method is carried out in the following manner:
As a pixel to be dithered shifts from (X, Y) to (X+1, Y+1), a corresponding index also shifts from (Px, Py) to (Px+1, Py+1). Then, when Px reaches DSx, Px returns to an initial value. Similarly, when Py reaches DSy, Py returns to an initial value. For example, it is assumed that DSx=4 and DSy=4, that all pixels of a two-dimensional multi-gradation image are dithered by repeating X-axis direction dithering in a Y-axis direction, and that initial coordinates of an index are (0, 0). In this case, as a pixel to be dithered changes, a corresponding index changes as (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), . . . , (3, 3), wherein the change of the index from (3, 0) to (0, 1) represents that Px returns to an initial value 0.
In the former modulo arithmetic method, however, the time-consuming division is required to be carried out. Thus, it is difficult to shorten the processing time. In the latter conditional branching method, every time a pixel (X, Y) to be dithered is changed, it is necessary to determine whether Px or Py of an index (Px, Py) corresponding to the pixel (X, Y) has reached the size of the dither matrix DSx or DSy, thereby to periodically initialize Px or Py. Such a determination, however, changes a subsequent process depending on its result. Therefore, if the conditional branching method is performed upon pipeline processing which aims at speed-up processing based on pre-reading of instructions, it may occur that the pre-read instructions are not executed depending on a result of the foregoing determination. Thus, the merits of the pipeline processing can not be fully exercised in the conditional branching method.
As described above, the modulo arithmetic method and the conditional branching method both have the common problem that it is difficult to shorten the processing time for determining an index corresponding to a pixel to be dithered next.